import java.util.Random;


public class AlgoritmosConsuta {

	/**
	 * @param args
	 */
	public static void main(String[] args) {

		final int rodadas = 30;
		final int tamanhoVetor = 10000;

		int[] vetorEntrada = new int[tamanhoVetor];
		int[] vetor = new int[tamanhoVetor];

		long tempoInicialSeq = 0;
		long tempoFinalSeq = 0;
		long tempoInicialBin = 0;
		long tempoFinalBin = 0;
		long acumuladoSeq = 0;
		long acumuladoBin = 0;

		vetor = gerarVetorOrdenado(tamanhoVetor);

		for (int i = 0; i < rodadas; i++) {

			vetor = gerarVetor(tamanhoVetor);

			for (int j = 0; j < vetor.length; j++) {
				tempoInicialSeq = System.nanoTime();
				consultaSequencial(vetorEntrada, vetor[j]);
				tempoFinalSeq = System.nanoTime();
				acumuladoSeq += tempoFinalSeq - tempoInicialSeq;

				tempoInicialBin = System.nanoTime();
				consultaBinaria(vetorEntrada, vetor[j]);
				tempoFinalBin = System.nanoTime();
				acumuladoBin += tempoFinalBin - tempoInicialBin;
			}

		}

		System.out.println("Consulta Sequencial: " + acumuladoSeq/rodadas);
		System.out.println("Consulta Binaria:    " + acumuladoBin/rodadas);

	}

	public static int[] gerarVetor(int tamanho) {

		Random gerador = new Random();
		int semente = 3000000;

		int[] vetor = new int[tamanho];

		int novoValor;
		int contador = 0;
		while (contador < tamanho) {
			novoValor = gerador.nextInt(semente);
			if (contador == 0) {
				vetor[contador] = novoValor;
				contador++;
			} else {
				for (int i = 0; i < contador; i++) {
					if (vetor[i] == novoValor) {
						break;
					} else if (i == contador-1) {
						vetor[contador] = novoValor;
						contador++;
					}
				}
			}
		}
		return vetor;
	}

	private static int[] gerarVetorOrdenado(int tamanho) {

		Random gerador = new Random();
		int semente = 3000000;

		int[] vetor = new int[tamanho];
		int[] vetorTemp = new int[tamanho];

		for (int j = 0; j < tamanho; j++) {
			int troca;
			vetorTemp = vetor;
			vetor[j] = gerador.nextInt(semente);
			for (int i = j; i >= 1; i--) {
				if (vetor[i] == vetor[i-1]) {
					vetor = vetorTemp;
					break;
				} else if (vetor[i] < vetor[i-1]) {
					troca = vetor[i];
					vetor[i] = vetor[i-1];
					vetor[i-1] = troca;
				}
			}
		}
		return vetor;
	}

	private static int consultaSequencial(int[] vetorEntrada, int chave) {
		int posicao = -1;
		for (int j = 0; j < vetorEntrada.length; j++) {
			if (chave == vetorEntrada[j]) {
				posicao = j;
				break;
			}
		}
		return posicao;
	}

	private static int consultaBinaria(int[] vetorEntrada, int chave) {
		int media;
		int posicao = -1;
		int inicio = 0;
		int fim = vetorEntrada.length;

		while (true) {

			if ((fim + inicio) % 2 == 0 ) {
				media = (fim + inicio)/2;
			} else {
				media = ((fim + inicio)/2) + 1;
			}

			if (inicio >= fim - 1 ) {
				inicio = 0;
				fim = vetorEntrada.length;
				break;
			} else if (chave < vetorEntrada[media]) {
				fim = media;
			} else if (chave > vetorEntrada[media]) {
				inicio = media;
			} else if (chave == vetorEntrada[media]) {
				inicio = 0;
				fim = vetorEntrada.length;
				posicao = media;
				break;
			}
		}
		return posicao;
	}

}
